public class Partition {
    public Node head;
    public Node partition(int x) {//按x值将链表分为两部分，然后连起来，顺序不变
    Node bs = null;
    Node be = null;
    Node as = null;
    Node ae = null;
    Node cur = this.head;
    while (cur != null) {
        if (cur.data < x) {
            //第一次插入
            if (bs == null) {
                bs = cur;
                be = cur;
            }
            //非第一次插入
            else {
                bs.next = cur;
                be = be.next;
            }
        } else {
            //第一次插入
            if (as == null) {
                as = cur;
                ae = cur;
            }
            //非第一次插入
            else {
                as.next = cur;
                ae = ae.next;
            }
        }
        cur = cur.next;
    }
    //1.判断bs是否为空，如果为空，返回as
    if (bs == null) {
        return as;
    }
    //2.如果bs不为空，进行拼接
    else {
        be.next = as;
        //3.如果as不为空，将ae的next置为空
        if(as!=null) {
            ae.next = null;
        }
        return bs;
    }
}
}
